package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午4:59:26
*/
public class Q28 {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if (m <= 0) {
            return false;
        }
        int n = matrix[0].length;
        if (n <= 0) {
            return false;
        }
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] <= target && matrix[i][n - 1] >= target) {
                return search(matrix[i], target);
            }
        }
        return false;
    }

    public boolean search(int a[], int target) {
        int left = 0;
        int right = a.length - 1;
        int point = -1;
        while (left <= right) {
            point = (right + left) / 2;
            if (a[point] > target) {
                right = point - 1;
            } else if (a[point] == target) {
                return true;
            } else {
                left = point + 1;
            }
        }
        return false;
    }

    @Test
    public void testA() {
        int[][] matrix = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 50 } };
        int target = 4;
        System.out.println(searchMatrix(matrix, target));
    }

}
